//1.回溯法
class Solution {
public:
    vector<int> st = vector<int>(10, 0);
    vector<int> flag = vector<int>(10, 0);
    vector<vector<int>> ret;
    void act_permute(vector<int>& nums, int u, int n) {
        vector<int> temp;
        if(u > n) {
            for(int i=1;i<=n;++i) {
                temp.push_back(st[i]);
            }
            ret.push_back(temp);
            temp={};
        }
        for(int i = 0; i < n; ++i) {
            if(flag[i]==1)
                continue;
            flag[i]=1;
            st[u]=nums[i];
            act_permute(nums,u + 1,n);
            flag[i]=0;

        }
        return ;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        
        int n = nums.size();
        act_permute(nums, 1, n);
        return ret;
    }
};

//2.
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<bool> used(n, false); //是否被使用
        dfs(nums, used);
        return res;
    }

    vector<vector<int>> res;
    vector<int> cur;
    
    void dfs(vector<int>& nums, vector<bool>& used) {
        int n = nums.size();
        if (cur.size() == n) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                cur.push_back(nums[i]);
                dfs(nums, used);
                cur.pop_back();
                used[i] = false;  // 回溯：标记为未使用
            }
        }
    }
};
